# This file is part of Gehyra.
#
# Gehyra is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# Gehyra is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Gehyra.  If not, see <http://www.gnu.org/licenses/>.

"""
@package gehyra.common.linkedlist
Implementation of linked lists. Gives constant insert/delete times.
$Id: linkedlist.py 451 2011-01-21 12:14:15Z andyhhp@gmail.com $
@todo: commemnt this file
"""

"""
@file gehyra/common/linkedlist.py
Implementation of linked lists. Gives constant insert/delete times.
"""

## @cond

# pylint: disable=C0111,W0622

from types import MethodType

class llist(object):
    __slots__ = ("val", "next")
NIL = llist() #: represents an empty linked list

# all the below hackery is so NIL can have type "llist"

def _llist____init__(self, value, next=NIL):
    self.val = value
    self.next = next

def _llist____iter__(self):
    next = self
    while next is not NIL:
        yield next.val
        next = next.next

def _llist__iternodes(self, stop=NIL):
    next = self
    while next != stop:
        yield next
        next = next.next

def _llist____str__(self):
    return "llist(%r, %s)" % (self.val, 'None' if self.next is NIL else '**')

def _llist__from_list(klass, lst):
    head = NIL
    for item in lst.__reversed__():
        head = llist(item, head)
    return head

# patch llist
llist.__init__ = MethodType(_llist____init__, None, llist)
llist.__iter__ = MethodType(_llist____iter__, None, llist)
llist.iternodes = MethodType(_llist__iternodes, None, llist)
llist.__str__ = MethodType(_llist____str__, None, llist)
# patch llist (classmethods)
llist.from_list = MethodType(_llist__from_list, llist, type(llist))

assert type(NIL) == llist

## @endcond

# pylint: enable=C0111,W0622
